//
//  Problem1436.swift
//  TestProject
//
//  Created by 武侠 on 2021/3/15.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 1436. 旅行终点站 key-value
 给你一份旅游线路图，该线路图中的旅行线路用数组 paths 表示，其中 paths[i] = [cityAi, cityBi] 表示该线路将会从 cityAi 直接前往 cityBi 。请你找出这次旅行的终点站，即没有任何可以通往其他城市的线路的城市。

 题目数据保证线路图会形成一条不存在循环的线路，因此只会有一个旅行终点站。

 示例 1：
     输入：paths = [["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]
     输出："Sao Paulo"
     解释：从 "London" 出发，最后抵达终点站 "Sao Paulo" 。本次旅行的路线是 "London" -> "New York" -> "Lima" -> "Sao Paulo" 。
 示例 2：
     输入：paths = [["B","C"],["D","B"],["C","A"]]
     输出："A"
     解释：所有可能的线路是：
     "D" -> "B" -> "C" -> "A".
     "B" -> "C" -> "A".
     "C" -> "A".
     "A".
     显然，旅行终点站是 "A" 。
 示例 3：
     输入：paths = [["A","Z"]]
     输出："Z"

 提示：
     1 <= paths.length <= 100
     paths[i].length == 2
     1 <= cityAi.length, cityBi.length <= 10
     cityAi != cityBi
     所有字符串均由大小写英文字母和空格字符组成。
 */
@objcMembers class Problem1436: NSObject {
    func solution() {
        print(destCity([["London","New York"],["New York","Lima"],["Lima","Sao Paulo"]]))
        print(destCity([["B","C"],["D","B"],["C","A"]]))
        print(destCity([["A","Z"]]))
        
        print(destCity([["jMgaf WaWA","iinynVdmBz"],["QCrEFBcAw","wRPRHznLWS"],["iinynVdmBz","OoLjlLFzjz"],["OoLjlLFzjz","QCrEFBcAw"],["IhxjNbDeXk","jMgaf WaWA"],["jmuAYy vgz","IhxjNbDeXk"]]))
    }
    
    
    /*
     1: 创建一个字典dic[String: String]
     2: 遍历路径数组，起始城市作为key，终点城市作为value，然后在把value作为key，""作为value
     3: 最后得到value是""的城市
     */
    func destCity(_ paths: [[String]]) -> String {
        var dp:[String: String] = [:]
        for path in paths {
            if dp[path[0]] == nil || dp[path[0]] == "" {
                dp[path[0]] = path[1]
            }
            if dp[path[1]] == nil {
                dp[path[1]] = ""
            }
        }
        
        for key in dp.values {
            if dp[key] == "" {
                return key
            }
        }
        
        print(dp)
        return ""
    }
}
